Authentication systems are used in computer systems to verify participants. For example, when a user logs into a computer (or ATM, etc.), an authentication system enables the computer to verify the identity of the user. Similarly, when a user is sending messages across an open network, the authentication system helps the recipient verify that the message truly originated from the user (and not an impostor) and was not subsequently altered.
One conventional authentication system is based on use of passwords or PINs (personal identification numbers). A user enters a password and the computer compares the password with a stored list of passwords. The computer permits access if the user supplied password matches the password stored at the system. The security of a password system is based on the premise that only the user knows his/her password. However, the password system must maintain a list of valid passwords on a storage disk that can be easily copied or physically stolen.
To mitigate the threat of theft, an improvement of the password system is to compute a one-way function of the password and store only those values. A list of passwords operated on by a one-way function is less useful to a thief because the one-way function cannot be reversed to recover the original passwords. Unfortunately, these lists are vulnerable to dictionary attacks, in which an attacker systematically guesses common passwords and operates on the guessed passwords with the one-way function. The results are compared to the list of passwords to determine if there are any matches. Dictionary attacks can be conducted very efficiently and comprehensively using computers.
Aspects of this invention are particularly concerned with authentication systems implemented on distributed computer networks having multiple clients and servers. In this context, it is desirable for an authentication system to accommodate both point-of-access authentication and authentication between participants who communicate over the network. Typically, participant authentication is achieved through use of cryptographic public key systems. Each participant has a unique private key that is kept secret and a corresponding public key that is published for all to know. The public/private key pair can be used to encrypt and decrypt messages bound for the participant, or to digitally sign messages on behalf of the participant, or to verify the participant's signature. Oftentimes, a participant might have several public/private key pairs for different cryptographic functions, including one key pair for encryption/decryption functions and one key pair for signing functions.
In a distributed network system, a user's private key is conventionally stored in the memory of the user's client computer. The user authenticates messages and performs other cryptographic functions from his/her personal machine using the private key. This poses a problem for a distributed network architecture because the user is restricted to his/her own computer. Ideally, the authentication system should permit a user to roam from machine to machine without losing the ability to access his/her private key(s), thereby enabling the user to perform cryptographic functions from any machine as if that machine was the user's own.
One conventional approach to a distributed authentication system is to encrypt each user's private key with that user's password and to store all encrypted keys at a centralized, publicly accessible server. To retrieve the private key, the user simply enters a password on any client computer. The encrypted key is fetched from the server and decrypted with the password. This prior art system has two significant drawbacks. First, an attacker can eavesdrop on the network and record the encrypted key as it is passed from the server to the client. The attacker can then perform an off-line dictionary attack on the encrypted key. A second drawback is that a publicly accessible server is required to maintain a large database of encrypted private keys, which provides a security weakness if the database is ever compromised. The threat becomes greater since this machine must be highly available online, increasing chances for attack.
Another approach is to store the user's private key on a secure portable device, such as a smart card. The user carries the smart card from machine to machine. At any particular machine, the user can insert his/her smart card into a card reader to perform log on. The smart card manages the private keys and prevents them from leaving the card in their raw form. This approach has two main drawbacks. The first drawback is that the cards are expensive. The second drawback is one of inconvenience, as the user is required to carry the smart card everywhere. Furthermore, since the majority of systems today do not have smart card readers, this approach is impractical in the short term.
Accordingly, there is a need for a distributed authentication system for a computer network which enables users to roam freely from machine to machine on the network and to regenerate their cryptographic key pairs at any one of the computers using only their password, without suffering from the drawbacks described above.